home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor1 / puzzle.doc < prev    next >
Text File  |  1995-03-31  |  3KB  |  76 lines
  1. (Comp.sys.handhelds) 
  2. Item: 803 by mcgovern at ee.su.oz.au 
  3. Author: [Hamish McGovern] 
  4.   Subj: puzzle-24 game for HP-48SX 
  5.   Date: Fri Sep 28 1990 07:55  
  6.  
  7. Here's a game I wrote (for hp-48sx) a couple of weeks ago but couldn't send 
  8. till now.  Its the puzzle-24 game.  I read that someone wrote 
  9. a similar program using the chip8 interpreter.  I thought I'd send this 
  10. anyway, it's rather hacked out and it's got a bug, but its still quite 
  11. playable. 
  12.  
  13. The problem is that it creates a random layout of the pieces and this  
  14. doesn't always result in a puzzle which can be solved.  About every second 
  15. puzzle is solvable.  I wonder if the guy that wrote puzzle-15 knows of 
  16. a test to see if the puzzle has a solution, or is the only way to do it 
  17. scrambling a completed puzzle.  The program RARR creates an array of 
  18. the number 1 to 24 in a random order, this is then used to place the 
  19. pieces on the board.  I wonder if some sort of test can be performed on  
  20. this to see if the puzzle will have a solution.  I thought maybe taking 
  21. the dot product with [1 2 ... 24 ] and testing if even, but this is not 
  22. correct. 
  23.  
  24. Load the directory PUZZLE, go into the the directory's CST menu, then 
  25. to play run PLAY and use the arrow keys to move a piece adjacent to the  
  26. empty square into that square.  Due to extreme lazyness on my behalf  
  27. you need to use key y^x as the down arrow ; i.e. 
  28.  
  29.                   ^ 
  30.                <     > 
  31.                  y^x           
  32.  
  33.  
  34.                     Hamish McGovern 
  35.                     mcgovern@ee.su.oz.au 
  36.  
  37. ------------ 
  38. (Comp.sys.handhelds) 
  39. Item: 813 by rcorless at uwovax.uwo.ca 
  40. Author: [Robert Corless] 
  41.   Subj: puzzle-24 for HP48-SX 
  42.   Date: Sat Sep 29 1990 11:13  
  43.  
  44. With regard to the solvability of the puzzle-24 game, I seem to 
  45. remember from my number-theory days (about 12 years ago now... sigh) 
  46. that the puzzle will be solvable precisely when you have written 
  47. the numbers down as an - even - permutation of the sequence 
  48. 1..24 (or n, if you like).  This is because the smallest exchange 
  49. you can make with the puzzle is a three-cycle. 
  50.  
  51. By "even permutation" I mean a permutation that can be written 
  52. as a product of three-cycles, and by "three-cycle" I mean a  
  53. permutation of the sort (1,2,3) -> (2,3,1).  These are called even 
  54. because every permutation can be written as a product of simple  
  55. exchanges, and every three-cycle needs 2 exchanges.  For example, 
  56. the above permutation is the product of 1<=>2 and 2<=>3.  It turns out that 
  57. exactly half of all permutations are even, so your observation 
  58. that half your games are solvable sounds spot-on. 
  59.  
  60. I seem to recall that the inventor of the 15-puzzle (he was 
  61. famous for puzzles) made a big splash by offering a big prize 
  62. for solving a particular puzzle - which, as he well knew, was 
  63. in the impossible half. 
  64.  
  65. I don't remember if there is a simple test for evenness of 
  66. a permutation.  It ought to be easy to write an "even" permutatation 
  67. generator, though.  Just start with the ordered set and perform  
  68. random three-cycles on it.  This is equivalent to starting with  
  69. your puzzle solved, I guess. 
  70.  
  71. --  
  72. ======== 
  73. Robert Corless, Applied Mathematics, University of Western Ontario 
  74. ========               London, Ontario, Canada N6A 5B9 
  75. e-mail    : RCORLESS@uwovax.uwo.ca 
  76.